public class Test1 {
    //leetcode 91 解码方法
    public int numDecodings(String ss) {
        //状态表示：dp[i]表示以第i个位置为结尾，有多少种解码方式
        //状态转移方程dp[i] = dp[i-1] + dp[i-2]
        char[] s = ss.toCharArray();
        int n = s.length;
        int[] dp = new int[n];
        //初始化
        dp[0] = (s[0] == '0' ? 0 : 1);
        if (n == 1) return dp[0];
        if (s[0] != '0' && s[1] != '0') dp[1] += 1;
        int t = (s[0] - '0') * 10 + (s[1] - '0');
        if (t >= 10 && t <= 26) dp[1] += 1;
        for (int i = 2; i < n; i++) {
            if (s[i] != '0') dp[i] += dp[i-1];
            int tt = (s[i-1] - '0') * 10 + (s[i] - '0');
            if (tt >= 10 && tt <= 26) dp[i] += dp[i-2];
        }
        return dp[n-1];
    }
}
